package 第5周_归并排序法.第一章归并排序法;

import 第1周_线性查找法.测试算法性能.ArrayGenerator;
import 第2周_排序基础.第一章选择排序法.SortingHelper;

import java.util.Arrays;

public class MergeSort {

    private MergeSort(){}

    public static <E extends Comparable<E>> void sort(E[] arr){
        sort(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r){
        //当左区间大于或等于右区间的时候，数组里面没有元素或者只有一个元素
        if (l >= r){
            return;
        }
        int mid = l + (r - l) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);

    }

    /**
     * 合并两个有序的区间 arr[l, mid] 和 arr [mid + 1, r]
     * @param arr
     * @param l 左边界索引
     * @param mid 中间索引
     * @param r 右边界索引
     * @param <E>
     */
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r){
        //因为是前闭后开区间，所以这里的索引是  r + 1
        E[] temp = Arrays.copyOfRange(arr, l, r + 1);

        int i = l, j = mid + 1;

        //每轮循环为 arr[k] 赋值
        for (int k = l; k <= r; k++){
            if (i > mid){
                arr[k] = temp[j - l];
                j++;
            }
            else if (j > r) {
                arr[k] = temp[i - l];
                i++;
            }
            else if (temp[i - l].compareTo(temp[j - l]) <= 0){
                arr[k] = temp[i - l];
                i++;
            }
            else{
                arr[k] = temp[j - l];
                j++;
            }
        }
    }

    public static void main(String[] args) {

        int n = 100000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
        SortingHelper.sortTest("MergeSort", arr);

    }

}
